//实现一个简单的顺序表
//直接以 int 为例，不写泛型

public class MyArrayList {
    //真正存储数据，顺序表本身就是基于数组的封装
    private int[] arr;
    //约定 arr 中的前 size 个元素，表示有效元素
    private int size = 0;

    // //////////////////////////////////
    //MyArrayList 的正式代码
    // /////////////////////////////////

    public MyArrayList() {
        arr = new int[10];
    }
    public MyArrayList(int capacity) {
        arr = new int[capacity];
    }

    //获取元素个数
    public int size() {
        return size;
    }

    //新增元素，尾插
    public void add(int val) {
        //把新的元素放到最后一个位置上，下标为 size 的位置
        //[0,size)
        if(size == arr.length) {
            //数组满了，需要先扩容再添加元素
                resize();
        }
        arr[size] = val;
        size++;
    }
    //扩容
    private void resize() {
        //1.创建一个更长的数组，容量扩展到1.5倍
        int[] newArr = new int[(int) (arr.length)];
        //int[] newArr = new int[arr.length + (arr.length >> 1)];
        //2.把原来数组的元素复制到新数组上
        for (int i = 0; i < size; i++) {
            newArr[i] = arr[i];
        }
        //3.用新的数组代替旧数组，旧的数组就会被垃圾回收释放掉
        arr = newArr;
    }
    //任意位置新增
    public void add(int index,int val) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index out of bounds");
        }
        //若数组已满，需要先扩容
        if (size == arr.length) {
            resize();
        }
        //搬运元素的操作，从后往前，依次把每个元素往后搬运一个元素
        //如果元素本身下标是i，就把这个元素赋值到i+1的位置上
        for (int i = size - 1; i >= index; i--) {
            arr[i+1] = arr[i];
        }
        arr[index] = val;
        //不要忘记更新 size
        size++;
    }
    //跟据下表获取元素
    public int get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("下标越界："+index);
        }
        return arr[index] ;
    }
    //跟据下标设置元素
    public void set(int index,int val) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("下标越界：" + index);
        }
        arr[index] = val;
    }
    //按照下标删除元素
    public int remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("下标越界" + index);
        }
        int result = arr[index];
        //该逻辑可以不需要，已经被涵盖在下面的代码中
//        if (index == size-1) {
//            //尾删
//            size--;
//            return result;
//        }
        for (int i = index; i < size-1; i++) {
            arr[i] = arr[i+1];
        }
        size--;
        return result;
    }
    //按照值删除元素
    public void delete(int val) {
//        //1.先找到值的位置
//        int index = 0;
//        for (index = 0; index < size; index++) {
//            if (arr[index] == val) {
//                //找到了
//                break;
//            }
//        }
//        if (index == size) {
//            //没有找到，元素不存在，不必进行删除了
//            return;
//        }

        int index = indexOf(val);
        if (index == -1) {
            return;
        }

        //2.然后通过上述 remove 的过程进行搬运式删除
        //   index 就是要删除的元素位置
//        for (int i = index; i < size-1; i++) {
//            arr[i] = arr[i+1];
//        }
//        size--;
        remove(index);
    }
    //判断元素是否存在
    public boolean contain(int val) {
        for (int i = 0; i < size; i++) {
            if (arr[i] == val) {
                return true;
            }
        }
        return false;
    }
    //查找元素的位置
    public int indexOf(int val) {
        for (int i = 0; i < size; i++) {
            if (arr[i] == val) {
                return i;
            }
        }
        return -1;
    }
    public int lastIndexOf(int val) {
        for (int i = size-1; i >= 0 ; i--) {
            if (arr[i] == val) {
                return i;
            }
        }
        return -1;
    }
    //清空
    public void clear() {
        //删除所有元素，逻辑删除即可1
        size = 0;
    }
    //打印操作,搞一个 toString ，把 MyArrayList 转化为字符串
    @Override
    public String toString() {
        StringBuffer stringBuffer = new StringBuffer();
        stringBuffer.append("[");
        for (int i = 0; i < size; i++) {
            stringBuffer.append(arr[i]);
            if(i < size - 1) {
                stringBuffer.append(",");
            }
        }
        stringBuffer.append("]");
        return stringBuffer.toString();
    }

    // ////////////////////////////////////
    //测试方法
    // ////////////////////////////////////

    private static void test1() {
        MyArrayList list = new MyArrayList();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        System.out.println(list.size());
        System.out.println(list);
    }

    private static void test2() {
        MyArrayList list = new MyArrayList(10);
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(0,100);
        list.add(1,200);
        list.add(2,300);
        System.out.println(list);
    }

    private static void test3() {
        MyArrayList list = new MyArrayList(10);
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        list.add(6);
        list.add(7);

        list.remove(0);
        System.out.println(list);
        list.remove(2);
        System.out.println(list);
        list.remove(4);
        System.out.println(list);
        list.remove(100);
        System.out.println(list);
    }

    private static void test4() {
        MyArrayList list = new MyArrayList(10);
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        list.add(6);

        list.delete(3);
        System.out.println(list);
        list.delete(5);
        System.out.println(list);
        list.delete(100);
        System.out.println(list);

//        System.out.println(list.contain(4));
//        System.out.println(list.indexOf(6));

        if (list.contain(3)) {
            System.out.println("ok");
        } else {
            System.out.println("failed");
        }
        if (!list.contain(100)) {
            System.out.println("ok");
        } else {
            System.out.println("failed");
        }
        if (list.indexOf(5) == 4) {
            System.out.println("ok");
        } else {
            System.out.println("failed");
        }
        if (list.indexOf(100) == 1) {
            System.out.println("ok");
        } else {
            System.out.println("failed");
        }
    }

    private static void test5() {
        MyArrayList list = new MyArrayList(10);
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        list.add(6);
        list.add(5);
        System.out.println(list.lastIndexOf(5));
       // System.out.println(list.clear());
    }

    public static void main(String[] args) {
        //test1();
        //test2();
        //test3();
        //test4();
        test5();
    }
}
